Search results for "000 Computer science"
showing 10 items of 18 documents
Variable time amplitude amplification and quantum algorithms for linear algebra problems
2012
Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. …
Computer Science Meets Ecology (Dagstuhl Seminar 17091)
2017
This report summarizes the program and main outcomes of the Dagstuhl Seminar 17091 entitled ``Computer Science Meets Ecolog''. Ecology is a discipline that poses many challenging problems involving big data collection, provenance and integration, as well as difficulties in data analysis, prediction and understanding. All these issues are precisely the arena where computer science is concerned. The seminar motivation was rooted in the belief that ecology could largely benefit from modern computer science. The seminar attracted scientists from both fields who discussed important topics in ecology (e.g. botany, animal science, biogeochemistry) and how to approach them with machine learning, co…
FO^2 with one transitive relation is decidable
2013
We show that the satisfiability problem for the two-variable first-order logic, FO^2, over transitive structures when only one relation is required to be transitive, is decidable. The result is optimal, as FO^2 over structures with two transitive relations, or with one transitive and one equivalence relation, are known to be undecidable, so in fact, our result completes the classification of FO^2-logics over transitive structures with respect to decidability. We show that the satisfiability problem is in 2-NExpTime. Decidability of the finite satisfiability problem remains open.
Detecting mutations by eBWT
2018
In this paper we develop a theory describing how the extended Burrows-Wheeler Transform (eBWT) of a collection of DNA fragments tends to cluster together the copies of nucleotides sequenced from a genome G. Our theory accurately predicts how many copies of any nucleotide are expected inside each such cluster, and how an elegant and precise LCP array based procedure can locate these clusters in the eBWT. Our findings are very general and can be applied to a wide range of different problems. In this paper, we consider the case of alignment-free and reference-free SNPs discovery in multiple collections of reads. We note that, in accordance with our theoretical results, SNPs are clustered in th…
Quine’s Fluted Fragment is Non-elementary
2016
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified by W.V. Quine. We show that the satisfiability problem for this fragment has non-elementary complexity, thus refuting an earlier published claim by W.C. Purdy that it is in NExpTime. More precisely, we consider, for all m greater than 1, the intersectionof the fluted fragment and the m-variable fragment of first-order logic. We show that this subfragment forces (m/2)-tuply exponentially large models, and that its satisfiability problem is (m/2)-NExpTime-hard. We round off by using a corrected version of Purdy’s construction to show that the m-variable fluted f…
Retrieving Monitoring and Accounting Information from Constrained Devices in Internet-of-Things Applications
2013
Part 6: Monitoring Mechanisms; International audience; Internet-of-Things (IoT) is envisioned to provide connectivity to a vast number of sensing or actuating devices with limited computational and communication capabilities. For the organizations that manage these constrained devices, the monitoring of each device’s operational status and performance level as well as the accounting of their resource usage are of great importance. However, monitoring and accounting support is lacking in today’s IoT platforms. Hence, this paper studies the applicability of the Constrained Application Protocol (CoAP), a lightweight transfer protocol under development by IETF, for efficiently retrieving monito…
Factors in the global assimilation of collaborative information technologies: an exploratory investigation in five regions
2008
The diffusion of innovation theory is deployed to investigate the global assimilation of collaborative information technologies (CITs). Based on the concepts of IT acquisition and utilization, an assimilation framework is presented to highlight four states (limited, focused, lagging, and pervasive) that capture the assimilation of conferencing and groupware CITs. Data collected from 538 organizations in the United States, Australia, Hong Kong, Norway, and Switzerland are aggregated and analyzed to explore assimilation patterns and the influence of decision-making pattern, functional integration, promotion of collaboration, organization size, and IT function size on the assimilation of CITs.…
K4-free Graphs as a Free Algebra
2017
International audience; Graphs of treewidth at most two are the ones excluding the clique with four vertices (K4) as a minor, or equivalently, the graphs whose biconnected components are series-parallel. We turn those graphs into a finitely presented free algebra, answering positively a question by Courcelle and Engelfriet, in the case of treewidth two. First we propose a syntax for denoting these graphs: in addition to parallel composition and series composition, it suffices to consider the neutral elements of those operations and a unary transpose operation. Then we give a finite equational presentation and we prove it complete: two terms from the syntax are congruent if and only if they …
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
2013
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of $n$ players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any $n$-player symmetric XOR game the entangled value of the game is $\Theta (\frac{\sqrt{\ln{n}}}{n^{1/4}})$ adapting an old result by Salem and Zygmund on the asymptotics of random tr…
On the Inner Product Predicate and a Generalization of Matching Vector Families
2018
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and mor…